/*
 * @Author: your name
 * @Date: 2024-05-09 14:47:23
 * @LastEditTime: 2024-05-10 21:43:31
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\131.分割回文串.cpp
 */
/*
 * @lc app=leetcode.cn id=131 lang=cpp
 *
 * [131] 分割回文串
 */

// @lc code=start
class Solution {
public:
    vector<vector<string>> res;
    vector<string> path;
    bool isHuiWen(const  string& s,int start, int end){
        while(start < end){
            if(s[start] != s[end]){
                
                return false;
            }
            else{
                start++;
                end--;
            }
        }
        return true;
    }
    void backtracking(string& s, int startIndex){
        if(startIndex >= s.size()){
            res.push_back(path);
            return;
        }

        for(int i = startIndex; i < s.size(); i++){
            if(isHuiWen(s, startIndex,i)){
                string str = s.substr(startIndex, i - startIndex + 1);
                path.push_back(str);
            }
            else{
                continue;
            }
            // 纵向
            backtracking(s, i + 1);
            path.pop_back(); // 回溯过程，弹出本次已经添加的子串
        }
    }
    vector<vector<string>> partition(string s) {
        backtracking(s, 0);
        return res;
    }
};
// @lc code=end

